#pragma once

#include <stdio.h>
#include <stdlib.h>
#include "heap.h"


HEAP::HEAP(unsigned int n) 
{
	size = 0;
    h = (ITEM*) malloc( sizeof(ITEM) * n);
}
    
HEAP::~HEAP() 
{
	if(h) free(h);
}

int HEAP::add(ITEM x) 
{
	h[++size]=x;
    checkup(size);
    return 1;
}

int HEAP::extract_min(ITEM *x) 
{
	if(size ==0) return 0;
    *x = h[1];
    h[1] = h[size--];
    checkdown(1);
    return 1;
}

void HEAP::checkup(int c) 
{
	int p;
    p = c / 2;
    if( p == 0 )return;
    if(h[p].key > h[c].key) 
	{
		ITEM tmp;
		tmp = h[p]; h[p] = h[c]; h[c] = tmp;
		checkup(p);
	}
}
    
void HEAP::checkdown(int p) 
{
	int c;
    c = 2*p;
    if( c > size ) return;
    if( c+1 <= size && h[c + 1].key < h[c].key ) c++;
    if( h[c].key < h[p].key ) 
	{
		ITEM tmp;
        tmp =  h[c]; h[c] = h[p]; h[p] = tmp;
        checkdown(c);
    }
}
